package org.example.dataStructure.linkedList;

/**
 * @author yuwl
 * @description
 * @since 2024-02-29 17:11
 */
public class SingleLinkedListTest {

    public static void main2(String[] args) {
        // 创建节点
        HeroNode n1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode n2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode n3 = new HeroNode(3, "吴用", "智多星");
        HeroNode n4 = new HeroNode(4, "林冲", "豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 加入链表
//        singleLinkedList.add(n1);
//        singleLinkedList.add(n4);
//        singleLinkedList.add(n2);
//        singleLinkedList.add(n3);

        singleLinkedList.addByOrder(n1);
        singleLinkedList.addByOrder(n4);
        singleLinkedList.addByOrder(n2);
        singleLinkedList.addByOrder(n3);


        //显示
        System.out.println("原始链表：");
        singleLinkedList.list();

        // 修改
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表：");
        singleLinkedList.list();

        // 删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);

        System.out.println("删除后的链表：");
        singleLinkedList.list();

        System.out.println("链表的有效节点个数：" + getLength(singleLinkedList.head));

        System.out.println("链表倒数第2个节点：" + findLastIndexNode(singleLinkedList.head, 2));
    }

    /**
     * 面试题：返回有效节点的个数
     * @param head
     * @return
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 面试题：查找链表倒数第K个节点
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);
        if (index <= 0 || index > length) {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < length - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 面试题：翻转链表
     * @param head
     * @return
     */
    public static HeroNode reverseListNode(HeroNode head) {
        // 下一个节点
        HeroNode next = null;
        // 前一个节点
        HeroNode prev = null;

        while (head != null) {
            // 临时保存下一个要翻转的节点
            next = head.next;
            // 将当前节点的下一个节点指向已经翻转的前一个节点（第一次翻转时会指向null）
            head.next = prev;
            // 保存已经翻转的节点
            prev = head;
            // 当前节点后移
            head = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "1", "1");
        HeroNode node2 = new HeroNode(2, "2", "2");
        HeroNode node3 = new HeroNode(3, "3", "3");
        HeroNode node4 = new HeroNode(4, "4", "4");
        HeroNode node5 = new HeroNode(5, "5", "5");
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println("原始链表：");
        System.out.println(node1);

        System.out.println("翻转后的链表：");
        System.out.println(reverseListNode(node1));
    }
}
